home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / graph_alg / _bellman_ford.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  1.8 KB  |  75 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _bellman_ford.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. /*******************************************************************************
  18. *                                                                              *
  19. *  BELLMAN FORD                                                                *
  20. *                                                                              *
  21. *******************************************************************************/
  22.  
  23. #include <LEDA/graph_alg.h>
  24. #include <LEDA/b_queue.h>
  25.  
  26.  
  27. bool BELLMAN_FORD(const graph& G, node s, const edge_array<num_type>& cost, 
  28.                                                 node_array<num_type>& dist, 
  29.                                                 node_array<edge>& pred ) 
  30.  
  31. /* single source shortest paths from s using a queue (breadth first search)
  32.    computes for all nodes v:
  33.    a) dist[v] = cost of shortest path from s to v
  34.    b) pred[v] = predecessor edge of v in shortest paths tree
  35. */
  36.  
  37. { 
  38.   node_data<int> count(G,0);
  39.  
  40.   int n = G.number_of_nodes();
  41.  
  42.   node_list Q;
  43.  
  44.   node u,v;
  45.   edge e;
  46.  
  47.   forall_nodes(v,G) 
  48.   { pred[v] = 0;
  49.     dist[v] = max_num; 
  50.    }
  51.  
  52.   dist[s] = 0;
  53.   Q.append(s);
  54.  
  55.   while(! Q.empty() )
  56.   { u = Q.pop();
  57.  
  58.     if (++count[u] > n) return false;   // negative cycle
  59.  
  60.     num_type du = dist[u];
  61.  
  62.     forall_adj_edges(e,u) 
  63.     { v = target(e);
  64.       num_type c = du + cost[e];
  65.       if (c < dist[v]) 
  66.       { dist[v] = c; 
  67.         pred[v] = e;
  68.         if (!Q.member(v)) Q.append(v);
  69.        }
  70.      } 
  71.    }
  72.   return true;
  73. }
  74.  
  75.